The present invention relates to a crossbar switch, having a plurality of input ports and a plurality of output ports, for sending messages input to the input ports to an selected output port. More particularly the present invention relates to a crossbar switch for use in a parallel computer having a plurality of computers connected to a switch type network and a broadcast communication method thereof for avoiding a deadlock between broadcast messages within the switch type network.
When a large amount of data is to be communicated in a parallel computer which performs data transfer between a plurality of processors (hereinafter called as nodes) through a network, it has been known to not transfer the data as one message, instead the message is divided into a plurality of parts of optional length, that are transferred as a plurality of messages. A "message" as used in the following description is intended to mean a message having an optional length.
An important data transfer function in the parallel computer is a broadcast function for transferring data in parallel from one node to a plurality of the nodes. However, when the parallel computer transfers messages between a plurality of nodes through a switch-type network, a deadlock sometimes occurs due to competition between the messages for use of the transfer path. Referring now to FIGS. 2 through 4, the general construction and operation of the conventional parallel computer will be described.
FIG. 2 illustrates a parallel computer in which four nodes are connected through four-input/four-output crossbar switch of one stage, FIG. 3 is a configuration view for illustrating a header decode circuit illustrated in FIG. 2, and FIG. 4 is configuration view for illustrating the priority controller illustrated in FIG. 2.
The parallel computer illustrated in FIG. 2 includes four nodes 11 to 14, a crossbar switch 10 with four input/output ports 0 to 3, and signal lines 150 to 153, 170 to 173, respectively. The node 11 includes a command processing device (IP) 101, a main memory device (MS) 102, a message receiving section (RCV) 103, a message transmission section (SND) 104. Each of the other nodes 12 to 14 can be constructed in the same way as the node 11. In this case, it is assumed that SND 104 performs a transfer of 1 word in one cycle. Each of the nodes 11 to 14 is connected to the crossbar switch 10 by input ports 0 to 3 through respective signal lines 150 to 153 and by output ports 0 to 3 through respective signal lines 170 to 173. The crossbar switch 10 includes a plurality of input buffers 105 to 108, header decode circuits 109 to 112, a priority controller 113, packet selector circuits 114 to 117, output buffers 118 to 121 and signal lines 154 to 169. The input buffers 105 to 108 and the header decode circuits 109 to 112 are arranged in correspondence with the input ports 0 to 3, and the packet selector circuits 114 to 117 and the output buffers 118 to 121 are arranged in correspondence with the output ports 0 to 3, respectively.
The operation of each of the composing elements of the crossbar switch 10 will be described as follows. The input buffers 105 to 108 receive messages from the nodes 11 to 14 through signal lines 150 to 153 and temporarily store the messages and thereafter performs a transferring of the messages to the output buffers 118 to 121 through packet selector circuits 114 to 117, respectively. The header decode circuits 109 to 112 receive the message words stored in the leading ends of the input buffers 105 to 108 from the input buffers 105 to 108 through signal lines 154 to 157, detect the message header and decode the message header. A priority controller 113 receives the message header information from the header decode circuits 109 to 112 through signal lines 158 to 161, performs issuing and adjustment of a request for use of an output port (request) and issues a message transmission-permit signal to the packet selector circuits 114 to 117 through signal lines 162 to 165.
Each of the packet selector circuits 114 to 117 receives a message from each of the input buffers 105 to 108 through signal lines 154 to 157 and transfers the message from the input buffer to which a signal of permission to transfer message is given in response to the message transmission allowable signal from the priority controller 113 to the output buffers 118 to 121. The output buffers 118 to 121 receive the message from the packet selector circuits 114 to 117 through the signal lines 166 to 169, temporarily store the message, thereafter transfer the message to the nodes 11 to 14 through the signal lines 170 to 173.
Then, referring to FIG. 3, the header decode circuit 109 will be described in detail. The other header decode circuits 110 to 112 are similarly constructed.
The header decode circuit 109 includes a message header register 201, a crossbar (XB) stage storing register 202, a synchronization latch 203, an AND circuit 204, a select circuit 205, a decode circuit 206, a broadcast register 207, a select circuit 208, an AND circuit 209 and signal lines 251 to 264. In this case, it is assumed that the message inputted from the node to the crossbar switch has a format as illustrated in FIG. 13 and includes a packet synchronization bit, a broadcast bit and an destination output port address for every stage of the crossbar switch under a multi-stage formation.
Accordingly, although the message header register 201 is revised every time a message word is transferred, the contents of the message header register 201 is valid only when a message word transmitted from the input buffer 105 is a leading word, namely a message header. Further, a packet synchronization bit is set to zero "0" at the leading end of the message and is set to one "1" at the trailing end of a message. The packet synchronization bit is kept at "1" all the time while the message has not completely reached the message header register 201. Accordingly, the time in which the content of the message header register 201 becomes effective is only a case in which the packet synchronization bit has been changed from "1" to "0". In addition, it is defined that a broadcast bit is set to "1" when the message is a broadcast message and is set to "0" when other messages are applied.
The stage number of each crossbar switch in a multi-stage configuration is stored in an XB stage configuration register 202. In this example, since the network includes one stage of crossbar switches, "0" is stored in the XB stage configuration register 202. A broadcast register 207 is provided with plural bits (4 bits in this example) corresponding to the number of output ports and "1" is stored in the bit corresponding to the port where the broadcast message is outputted. In this example, it is assumed that the broadcast is performed for all the nodes and "1111" is stored in the broadcast register 207. In addition, the signal lines 251 and 264 are bundled and connected to a priority controller 113 as a 5-bit signal line 158.
The message header register 201 receives a message word from the input buffer 105 through the signal line 154. The contents of the header register 201 is revised every cycle. The synchronization latch 203 receives a packet synchronization bit within a message word through a signal line 251 and keeps the packet synchronization bit for 1 cycle. An AND circuit 204 receives an inverting signal of a packet synchronization bit within the message word through the signal line 251 and at the same time receives the packet synchronization bit of the previous cycle from the synchronization latch 203 through the signal line 258. The AND circuit 204 detects whether the packet synchronization bit changes from "1" to "0" so as to discriminate the message header, generates a header discriminating signal and transmits the header discriminating signal to the signal line 259. The select circuit 205 receives each of the destination output port addresses of stages "0" to "3" in the message header register 201 through signal lines 253 to 256, receives the number of stages in the crossbar switch from the XB stage configuration register 202 through a signal line 257 and selects an destination output port address. In this example, the select circuit 205 selects the destination output port address of the stage 0. The decode circuit 206 receives the destination output port address from the select circuit 205 through a signal line 260 and decodes it to a signal of "1" of the bit corresponding to the aforesaid destination output port address with a bit width of for example 4 bits corresponding to the number of output ports.
The select circuit 208 receives the destination output port address decoded from the decode circuit 206 through a signal line 261 and further receives an output port of the broadcast message from the broadcast register 207 through a signal line 262, respectively. The select circuit 208 additionally receives the broadcast bit within the message word as a select signal through a signal line 252. When the broadcast bit is "1", the select circuit 208 selects an output from the broadcast register 207, and when the broadcast bit is "0", the select circuit 208 selects an output from the decode circuit 206 as an output destination output port address signal, respectively. AND circuit 209 receives an output destination output port address signal from the select circuit 208 through a signal line 263 and a header discriminating signal from AND circuit 204 through a signal line 259, respectively. Only when the message word being transmitted from the input buffer 105 is a message header, is an output destination output port address signal output to the signal line 264. The output destination output port address signal (4 bits) of the signal line 264 and the packet synchronization bit (1 bit) of the signal line 251 are given to the priority controller 113 as message header information through the signal line 158.
Referring to FIG. 4, the priority controller 113 will be described in detail. The priority controller 113 includes request issuing circuits 31 to 34, request adjustment circuits 35 to 38, and signal lines 350 to 354, 360 to 364, 370 to 374, 380 to 384, 390 to 394. Each request issuing circuit 31 to 34 is arranged to correspond to the input ports "0" to "3" and each request adjustment circuit 35 to 38 is arranged to be corresponded to the output ports 0 to 3, respectively. The request issuing circuit 31 includes an output destination output port address register 301. The request issuing circuits 32 to 34 each have a similar construction. The request adjustment circuit 35 includes a request latch 302, a counter latch 303, a decode circuit 304, AND circuit 305, OR circuit 306, a 2-bit counter 307 and signal lines 355 to 359. The request adjustment circuits 36 to 38 each have a similar construction.
As described above, the output destination output port address signal in this example has 4 bits and the output destination output port address register 301 of the request issuing circuit 31 has 4 corresponding registers. The output destination output port address signal in the message header information is stored through a signal line 264 included in a signal line 158. Each of the output destination output port address registers 301 is connected to signal lines 350 to 380 for every bit so as to output a request signal to each of the corresponding output ports. A packet synchronization bit in a signal line 251 included in the signal line 158 is output to a signal line 390 as it is. Other request issuing circuits 32 to 34 are constructed similar to the request issuing circuit 31. A signal line 354 is constructed such that four signal lines 350 to 353 corresponding to the output port 0 in each of the request issuing circuits 31 to 34 are bundled together to form a 4-bit signal line. Similarly signal lines 364, 374 and 384 are signal lines in which each of the signal lines 360 to 363 correspond to the output port 1. Signal lines 370 to 373 correspond to the output port 2 and signal lines 381 to 383 correspond to the output port 3. Each of these sets of signal lines are bundled together to form four bits. The signal line 394 is a signal line including four signal lines 390 to 393 each providing a packet synchronization bit from the request issuing circuits 31 to 34. These signal lines are bundled together to form four bits.
Each of request latches 302 of a request adjustment circuit 35 corresponding to the output port "0" is correspondingly arranged for every input ports "0" to "3", i.e. in correspondence with the request issuing circuits 31 to 34 and the latches are constructed by four latches. AND circuit 305 is also similarly constructed to have four AND circuits. Each signal line of the bundled signal lines 354 is connected to a terminal of a latch which forms a part of the request latch 302. Each latch of the request latch 302 corresponds to the input ports. Each signal line of the bundled signal lines 394 is connected to the reset terminals of each latch of the request latch 302. A signal line 162 is a signal line in which four outputs of each AND circuit of AND circuit 305 are bundled together. The signal line 162 provides a message transmission allowable signal corresponding to an input port to issue output of a message to an output port. This signal is transmitted to the packet selector circuit 114 shown in FIG. 2. Request adjustment circuits 36 to 38 corresponding to the output ports 1 to 3 are each constructed similar to the request adjustment circuit 35.
Each of the request issuing circuits 31 to 34 corresponding to each of the input ports receives a message header information from each of the header decode circuits 109 to 112 corresponding to each of the input ports shown in FIG. 2 through signal lines 158 to 161. Each of the request signals from the request issuing circuit 31 to 34 is issued to each of the request adjustment circuits 35 to 38 corresponding to each of the output ports. A packet synchronization bit is output to the signal lines 390 to 393. The request adjustment circuits 35 to 38 receive each of the request signals from the request issuing circuits 31 to 34 through each of signal lines 354, 364, 374 and 384. Also a packet synchronization bit is inputted through the signal line 394. A request adjustment processing is carried out by the request adjustment circuit 35-38. Each of message transmission-permit signals corresponding to an input port and an output port is transmitted to the packet selector circuits 114 to 117 through signal lines 162 to 165, respectively.
Now, operation of each of the components will be described in reference to the request issuing circuit 31 and the request adjustment circuit 35. The output destination output port address register 301 in the request issuing circuit 31 receives an output destination output port address signal from the header decode circuit 109 through a signal line 264. The output destination output port address signal is stored for every bit corresponding to the output port. Each of the request issuing circuits 31 to 34 outputs a request signal to each of the request adjustment circuits 35 to 38 through signal lines 350, 360, 370 and 380, respectively. A request latch 302 corresponding to each of the input ports within the request adjustment circuit 35 inputs a request signal from each of the request issuing circuits 31 to 34 as a set signal through a signal line 354. The request latch 302 also inputs a synchronous signal as a reset signal through the signal line 394. A request from each of the input ports is held until the packet synchronization bit becomes "1". A counter latch 303 receives an output signal of a 2-bit counter 307 through a signal line 359 and holds an input port number for performing an adjustment of the request. The decode circuit 304 receives an output from the counter latch 303 through a signal line 356 and decodes it into 4 bits.
AND circuit 305 corresponding to each of the input ports inputs each of the requests held in the request latch 302 through a signal line 355, and inputs each of decode output signals of the decode circuit 304 through a signal line 358. The AND circuit 305 transmits a message transmission-permit signal corresponding to the input port to the packet selector circuit 114 through a signal line 162 when a request is issued from the input port having a number indicated by the counter latch 303. The signal line 162 is constructed of four bits, wherein the message transmission-permit signal corresponding to the input port 0, for example, becomes "0001". OR circuit 306 receives an output (message transmission-permit signal) from each of AND circuits 305 through a signal line 162 and takes its OR. A 2-bit counter 307 receives an output signal from the counter latch 303 through a signal line 356, receives an output signal from the OR circuit 306 as a count signal (CN) through a signal line 357. The 2-bit counter 307 continues its counting operation during a period in which the message transmission-permit signal is not transmitted and interrupts its counting operation until the transmission of the message is completed when the message transmission-permit signal is not transmitted. Namely, the 2-bit counter 307 re-starts a counting operation when the message transmission of input port number indicated by the counter latch 303 is completed, a signal corresponding to the request latch 302 is reset and a corresponding output of the AND circuit 305 becomes "0". Thus, the result is that an output of the OR circuit 306 becomes "0", respectively.
Then, a flow of operation within the crossbar switch 10 will be described more practically in reference to the case in FIG. 2 in which the node 11 transmits a normal one-to-one communication message (hereinafter called a normal message) for the node 11 (stage 0, destination output port address 0).
A normal message transmitted from SND 104 of the node 11 to the crossbar switch 10 is stored temporarily in the input buffer 105 of the input port "0" through the signal line 150. The leading word of the message within the input buffer 105 is inputted to the header decode circuit 109 through the signal line 154 so as to cause a decode operation of the header to be carried out.
At the message header register 201 within the header decode circuit 109 shown in FIG. 3, at first, the packet synchronization bit is changed from "1" to "0"' concurrent with an arrival of the message. The message header is discriminated by AND circuit 204 and the header discrimination signal is asserted. As described above, since an output from the XB stage configuration register 202 is "0", the destination output port address ("0" in this example) in the stage "0" within the message header register 201 is selected at the select circuit 205. The destination output port address signal is decoded to "0001" at the decode circuit 206 and then input to the select circuit 208. When the message to be transmitted is a normal message, the broadcast bit in the message header register 201 is "0" and an output "0001" of the decode circuit 206 is selected at the select circuit 208 as the output destination output port address signal. Since the header discriminating signal is asserted, AND circuit 209 is turned ON. Thus, the output destination output port address signal "0001" in the select circuit 208 is output to the signal line 264. The destination output port address signal is transmitted to the priority controller 113 as message header information together with the packet synchronization bit in the signal line 251 through the signal line 158.
Since portions of a message transmitted from the input buffer 105 through the signal line 154 is varied for every cycle during transmission of the message, the content in the message header register 201 is revised for every cycle and the output of the select circuit 208 is varied. However, the header discriminating signal is not asserted other than at the leading end of the message. Thus, AND circuit 209 is kept OFF and the output signal for the priority controller 113 is kept at "0". The packet synchronization bit is not changed at all.
At the request issuing circuit 31 within the priority controller 113 shown in FIG. 4, the output destination output port address signal so provided by the signal line 264, included in the signal line 158, is divided for every output port and stored in the output destination output port address register 301. Then a request is issued to the request adjustment circuit 35 through signal lines 350, 354. When no request is issued from the other request issuing circuits 32 to 34, a signal transmitted at the signal line 354 becomes "0001". The request adjustment circuits 35 to 38 receives the requests from issued the request issuing circuits 31 to 34. An adjustment processing for a request issued by the request issuing circuits 31 to 34 is carried out in a round-robin manner. At the request adjustment circuit 35, upon receiving a request from the request issuing circuit 31, the latch corresponding to the input port 0 of the request latch 302 is set. When an input is "0", indicating no request being issued, the 2-bit counter 307 performs a counting operation. An output of the 2-bit counter 307 is provided to a counter latch 303. An output of the counter latch 303 continually revises its contents from "0" to "3" based on the count from the 2-bit counter 307. As the latch of the request latch 302 corresponding to the input port 0 of the request latch 302 is set, the 2-bit counter counts "0". When the value of the counter latch 303 becomes "0", an output of a decode circuit 304 becomes "0001". Therefore, an output of AND circuit 305 corresponding to the input port 0 becomes "1". Then a message transmission-permit signal ("0001") for the input port 0 is transmitted to the packet selector circuit 114 of the output port 0 through the signal line 162. Concurrently, since the output of OR circuit 306 becomes "1", the counting operation of the 2-bit counter 307 is temporarily stopped.
Upon receiving the message transmission-permit signal ("0001") for the input port 0, the packet selector circuit 114 changes over an internal switch in such a way that an output of the input buffer 105 of the input buffers 105 to 108 can be inputted to the output buffer 118 so as to start a transmission of message from the input port 0. The message is temporarily stored in the output buffer 118. Thereafter, the message is transmitted to RCV 103 of the node 11 through the output port 0 and the signal line 170. Upon completion of the transmission of the message from the input buffer 105, the packet synchronization bit in the message header register 201 within the header decode circuit 109 becomes "1". A latch corresponding to the port 0 of the request latch 302 of the request adjustment circuit 35 within the priority controller 113 is reset through signal lines 251, 390 and 394. AND circuit 305 is turned OFF and the output of OR circuit 306 becomes "0". Thus, the 2-bit counter 307 starts to count again.
Although the foregoing is an operation of the crossbar switch 10 when a normal message is inputted from one node. If plural normal messages are inputted concurrently from a plurality of nodes to the crossbar switch 10 and requests from a plurality of input ports are issued concurrently to the same request adjustment circuit within the priority controller 113, then the messages can be transmitted without any problem by performing a sequential processing of the requests within the request adjustment circuit using a round robin process. Namely, when "1" (for example, "1010") is produced in a plurality of latches in the request latch 302 shown in FIG. 4, only one "1" is included in the output of the decode circuit 304. Further, during a period in which a message transmission-permit signal is applied to one input port, the counting operation of the 2-bit counter 307 is stopped and the output from the decode circuit 304 is not changed. Thus, the message transmission-permit signal is not concurrently set for a plurality of input ports. Due to this fact, the message at any input port (for example, port 1) is processed at first and another message at the another port (for example, port 3) is caused to wait within the input buffer until completion of the transmission. Thus, the system tends to avoid a deadlock state in which both messages are not transmitted.
Referring to FIG. 2, an operation in the crossbar switch 10 when a broadcast message is transmitted from the node 11 will be described.
The leading word of the message stored in the input buffer 105 from the node 11 is decoded at the header decode circuit 109 shown in FIG. 3 in the same manner as that for a normal message. The broadcast bit when a broadcast message is to be transmitted set to "1". Thus, at the select circuit 208, the output ("1111") of the broadcast register 207 is selected as an output destination output port address signal in place of the decode value at the destination output port address in the message header register 201. This output destination output port address signal is transmitted to the priority controller 113 together with the packet synchronization bit through the signal line 158.
At the request issuing circuit 31 within the priority controller 113 shown in FIG. 4, all the bits in the output destination output port address register 301 become "1". Thus, a request is issued to the request adjustment circuits 35 to 38 for all the output ports. An adjustment processing with respect to the request is carried out in the same manner as that for a normal message within each of the request adjustment circuits 35 to 38. Then the message transmission-permit signal for the input port "0" is transmitted to each of the packet selector circuits 114 to 117.
At each of the packet selector circuits 114 to 117, an internal switch is changed over in such a way that an output of the input buffer 105 is inputted to each of the output buffers 118 to 121. After the switch change over operation is carried out in all the packet selector circuits, the transmission of the broadcast message is started at once for each of the output ports 0 to 3.
The foregoing is an operation within the crossbar switch 10 when a broadcast message is transmitted from one node. For this situation the system may not be set to the deadlocked state. However, when the broadcast message is input concurrently to a plurality of input ports, there is a possibility that the deadlock state can occur.
The occurrence of the deadlock will be described in reference to a situation where the broadcast message is issued concurrently from the nodes 11 and 13 as shown in FIG. 2. In this case, each of the broadcast messages is stored in the input buffers 105 and 107. Thereafter, each of the requests is issued to each of the request adjustment circuits 35 to 38 from the request issuing circuits 31 and 33 within the priority controller 113 through header decode circuits 109 and 111 based on the leading words in the messages. At each of the request adjustment circuits 35 to 38, an adjustment processing is carried out in the same manner as that of a normal message. Thereafter, the message transmission-permit signal for any one of the input ports is transmitted for the packet selector circuits 114 to 117.
In the above-described situation a problem may occur in that a request processed in advance in each of the request adjustment circuits is different from the former one. For example, when the request for the input port 0 is processed at the request adjustment circuits 35 to 37 and the request for the input port 2 is processed at the request adjustment circuit 38, a message transmission-permit signal for the input port 0 is issued to the packet selector circuits 114 to 116 and a message transmission-permit signal for the input port 2 is issued to the packet selector circuit 117. As described above, the transmission of the broadcast message can not be started until the message transmission-permit signal from all the input ports has been issued and applied to the appropriate packet selector circuits. Thus, the message at the input port 0 waits for application of the message transmission-permit signal for the input port 0 to the packet selector circuit 117. Further, the message for the input port 2 waits for the message transmission-permit signal for the input port 2 applied to the packet selector circuits 114 to 116. The result is that both ports may not transmit their messages and also release the output ports. Therefore, the crossbar switch is set to a deadlocked state, thereby preventing transmission of messages.
The foregoing relates to a description of the deadlock state generated in a network constructed of a one stage crossbar switch. When the network is constructed of a multi-stage crossbar switches, the deadlock state occurs more readily. In this case, occurrence of the deadlock will be described in reference to the system in which the crossbar switch 10 illustrated in FIGS. 2 to 4 is constructed by 2.times.2 stages as illustrated in FIG. 12.
The system illustrated in FIG. 12 includes a plurality of nodes 801 to 808, crossbar switches 809 to 812 and signal lines 850 to 873. The nodes 801 to 808 are constructed in the same manner as the node 11 illustrated in FIG. 2. The crossbar switches 809 to 812 are constructed in the same manner as the crossbar switch 10 illustrated in FIGS. 2 through 4. The nodes 801 to 804 are connected to the crossbar switch 809 through each of the signal lines 850 to 853, and to the crossbar switch 811 through each of the signal lines 866 to 869, respectively. The nodes 805 to 808 are connected to the crossbar switch 810 through each of the signal lines 854 to 857, and to the crossbar switch 812 through each of the signal lines 870 to 873. The crossbar switch 809 is connected to the crossbar switch 811 through the signal lines 858 and 859, and to the crossbar switch 812 through the signal lines 862 and 863. The crossbar switch 810 is connected to the crossbar switch 811 through the signal lines 860 and 861, and to the crossbar switch 812 through the signal lines 864 and 865, respectively. Operations in each of the nodes and each of the crossbar switches are performed in the manner described in reference to FIGS. 2 through 4.
At first, the operation when the node 801 issues a broadcast message will be described. The broadcast message issued from the node 801 is input to the crossbar switch 809 through the signal line 850. The crossbar switch performs request issuing and request adjustment processings and then transmits the message to the crossbar switches 811 and 812. Transmission of the message toward the crossbar switch 811 is set by applying only one of the output port 0 (the signal line 858) or the output port 1 (the signal line 859). Which one of the output ports to be used is set by the broadcast register 207 within the header decode circuit illustrated in FIG. 3. A path for the crossbar switch 812 is similarly, wherein it is assumed that each of the output port 0 (the signal line 858) and the input port 2 (the signal line 862) is used. A broadcast message transmitted from the crossbar switch 809 to the crossbar switch 811 through the signal line 858 is similarly processed within the crossbar switch 811. The broadcast message is transmitted from all the output ports of the crossbar switch 811 to the nodes 801 to 804 through the signal lines 866 to 869. Also at the crossbar switch 812, the broadcast message input through the signal line 862 is transmitted from all the output ports to the nodes 805 to 808 through the signal lines 870 to 873. The execution of the broadcast is then completed.
A case where a broadcast is executed at the node 805 before executing a broadcast at the node 801 will be considered. It is assumed that the broadcast message issued from the node 805 is input to the crossbar switch 810 through the signal line 854 and further inputted each of the crossbar switches 811 and 812 from the output ports 0 and 2 through each of the signal lines 860 and 864. At this time, if a previous message is left in the input buffer of the input port 2 of the crossbar switch 812 under a state to wait for adjustment processing or during its transmission, a broadcast message is transmitted only by an amount corresponding to the vacant volume of the output buffer of the output port 2 of the crossbar switch 810 and the input buffer of the input port 2 of the crossbar switch 812. If the amount of the message is larger than the vacant volume, the transmission of the message is temporarily stopped until the previous message is processed. Since the transmissions of the broadcast message for each of the output ports are performed concurrently, the transmission for the crossbar switch 811 is also interrupted. In this case, since the operation is in the midway part of message transmission, the output ports 0 and 2 of the crossbar switch 810 are not released until the transmission of the broadcast message is completed.
The broadcast message transmitted from the crossbar switch 810 to the crossbar switch 811 through the signal line 860 before the transmission is interrupted occupies all the output ports just after adjustment processing. When there is no other message to be processed at the crossbar switch 811, the transmission to the nodes 801 to 804 is started. The crossbar switch 811 can also interrupt the transmission of the message when its output port is being occupied after transmitting a message corresponding to the amount transmitted from the crossbar switch 810.
Under this state, if the node 801 starts to execute a broadcast, the broadcast message from node 801 is transmitted to the crossbar switch 811 from the crossbar switch 809 through the signal line 858. All the output ports of crossbar switch 811 are occupied by the broadcast message from the node 805. Thus, only messages corresponding to the vacant volume of the output buffer of the output port 0 of the crossbar switch 809 and the input buffer of the input port 0 of the crossbar switch 811 is transferred and its processing is temporarily interrupted. In turn, the broadcast message transferred from the output port 2 of the crossbar switch 809 through the signal line 862 is stored in the input buffer of the input port 0 of the crossbar switch 812 so as to issue the request.
When the message left in the input port 2 of the crossbar switch 812 is completely transferred, the broadcast message from the node 801 which reached the input port 0 prior to the broadcast message from the node 805 is processed. Then transferred messages from crossbar switch 809 after performing an adjustment processing are transmitted from all the output ports to the nodes 805 to 808 through the signal lines 870 to 873. Although at the crossbar switch 809, since the transmission of the message is interrupted, the broadcast message is not allowed to flow to the last crossbar switch. Due to this fact, after the transferred message is transmitted, the crossbar switch 812 also interrupts the transmission while occupying the output port. In this way, since all the crossbar switches 809 to 812 interrupt the transmission of the broadcast message while occupying the output ports, it is not possible to transfer a message more than a set volume. Thus, a deadlock state results.
In order to avoid such a deadlock as described above, a first node for executing a broadcast is allowed to execute the broadcast while a second node for executing another broadcast must be prevented from executing the broadcast and required a procedure in which the replacement broadcast is executed. Thus, the software over head for executing the replacement broadcast and storage for storing the messages for later broadcast causes a substantial increase in the load of the nodes. Therefore, processing performance of the entire system may be reduced.
As a method for solving this problem, Japanese Patent Laid-Open No. Hei 7-262155 shows a method wherein the replacement broadcast operation is not performed by the node, but performed by a specified relay switch. In this method, at least one specified relay switch not receiving the broadcast message is set in addition to a relay switch installed at a grid point of an array type network. When the broadcast request message passes through the specified relay switch, it is changed into a broadcast message and transmitted to all the nodes. Thus, the deadlock is avoided without applying any load to the nodes and a fast broadcast function can be realized.
The above-described method for arranging the specified relay switch has some problems. That is, an amount of hardware for preparing a specified relay switch not connected to the node and an expansion crossbar switch for connecting the switch is increased. Also, there is no apparatus for performing an alternative function when malfunctions occur. Further, since all the broadcast request messages pass through the specified relay switch, a transmission path for the broadcast message is fixed. This results in an increase in the load at the specified path. Thus, performance is reduced.